#define _CRT_SECURE_NO_WARNINGS 1
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<unordered_map>
using namespace std;

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> arr(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1] + mat[i - 1][j - 1] - arr[i - 1][j - 1];
            }
        }

        vector<vector<int>> ret(n, vector<int>(m));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int x1 = max(0, i - k) + 1;
                int y1 = max(0, j - k) + 1;
                int x2 = min(n - 1, i + k) + 1;
                int y2 = min(m - 1, j + k) + 1;
                ret[i][j] = arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] + arr[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
};

int main() {
    return 0;
}